package com.xiaoxin.sort;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * <p>Description: 
 * 	排序：1、内部排序：
 * 			使用内存中进行排序；
 * 			1)、插入排序（直接插入和希尔排序）
 * 			2)、选择排序（简单选择排序和堆排序）
 * 			3)、交换排序（冒泡排序和快速排序）
 * 			4)、归并排序
 * 			5)、基数排序
 * 		2、外部排序：
 * 			使用内存和磁盘进行排序；
 * </p> 
 * @author 肖鑫
 * @date 2019年3月2日
 * 
 */
public class Sort {
	private static int[] array = { -1, 2, 3, -4, 5, 6, 2, 3, 2 };
	private static ArrayList<Integer> list = new ArrayList<>();
	static {
		for (int i = 0; i < array.length; i++) {
			int j = array[i];
			list.add(j);
		}
	}
	public static void main(String[] args) {
		System.out.println("排序前：");
		for (int i = 0; i < array.length; i++) {
			System.out.print(array[i] + ",");
		}
		System.out.println();
		
//		bubbleSort(array);
//		selectionSort(array);
//		insertionSort(array);
//		shellSort(array);
//		mergeSort(array);
//		quickSort(array, 0, array.length);
//		heapSort(array);
//		countingSort(array);
//		bucketSort(list);
//		radixSort(array);
		
		System.out.println("排序后：");
		for (int i = 0; i < array.length; i++) {
			System.out.print(array[i] + ",");
		}
		System.out.println();

	}

	/**
	 * <p>冒泡排序
	 * <p>算法描述：
	 * <p>1、比较相邻的元素。如果第一个比第二个大，就交换它们两个；
	 * <p>2、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数； 
	 * <p>3、针对所有的元素重复以上的步骤，除了最后一个；
	 * <p>4、重复步骤1~3，直到排序完成。 
	 * <p>算法分析 最佳情况：T(n) = O(n) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(n2)
	 * 
	 * @param array
	 */
	public static void bubbleSort(int[] array) {
		if (array.length == 0) {
			System.out.println("数组为空");
		} else {
			for (int i = 0; i < array.length; i++) {
				for (int j = 0; j < array.length - i - 1; j++) {
					if (array[j + 1] > array[j]) {
						int temp = array[j + 1];
						array[j + 1] = array[j];
						array[j] = temp;
					}
				}
			}
		}
	}
	
	/**
	 * <p>选择排序 
	 * <p>算法描述：
	 * <p>1、初始状态：无序区为R[1..n]，有序区为空；
	 * <p>2、第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
	 * <p>3、n-1趟结束，数组有序化了。 
	 * <p>算法分析 最佳情况：T(n) = O(n2) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(n2)
	 * 
	 * @param array
	 */
	public static void selectionSort(int[] array) {
		if (array.length == 0) {
			System.out.println("数组为空");
		} else {
			for (int i = 0; i < array.length; i++) {
				int maxIndex = i;
				for (int j = i; j < array.length; j++) {
					if (array[j] > array[maxIndex]) {
						maxIndex = j;
					}
				}
				int temp = array[maxIndex];
				array[maxIndex] = array[i];
				array[i] = temp;
			}
		}
	}
	
	/**
	 * <p>插入排序 
	 * <p>算法描述： 
	 * <p>1、从第一个元素开始，该元素可以认为已经被排序； 
	 * <p>2、取出下一个元素，在已经排序的元素序列中从后向前扫描；
	 * <p>3、如果该元素（已排序）大于新元素，将该元素移到下一位置； 
	 * <p>4、重复步骤3，直到找到已排序的元素小于或者等于新元素的位置； 
	 * <p>5、将新元素插入到该位置后；
	 * <p>6、重复步骤2~5。 
	 * <p>算法分析 最佳情况：T(n) = O(n)   最坏情况：T(n) = O(n2)   平均情况：T(n) = O(n2)
	 * 
	 * @param array
	 */
	public static void insertionSort(int[] array) {
		if (array.length == 0) {
			System.out.println("数组为空");
		} else {
			int current;
			for (int i = 0; i < array.length - 1; i++) {
				current = array[i + 1];
				int prevIndex = i;
				while (prevIndex >= 0 && current > array[prevIndex]) {
					array[prevIndex + 1] = array[prevIndex];
					prevIndex--;
				}
				array[prevIndex + 1] = current;
			}
		}
	}
	
	/**
	 * <p>希尔排序 
	 * <p>算法描述：
	 * <p>1、选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1； 
	 * <p>2、按增量序列个数k，对序列进行k 趟排序；
	 * <p>3、每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1时，整个序列作为一个表来处理，表长度即为整个序列的长度。 
	 * <p>算法分析 最佳情况：T(n) = O(nlog2 n) 最坏情况：T(n) = O(nlog2n) 平均情况：T(n) =O(nlog2n)
	 * 
	 * @param array
	 */
	public static void shellSort(int[] array) {
		int length = array.length;
		int current, gap = length / 2;
		if (length == 0) {
			System.out.println("数组为空");
		} else {
			while (gap > 0) {
				for (int i = gap; i < length; i++) {
					current = array[i];
					int prevIndex = i - gap;
					while (prevIndex >= 0 && current > array[prevIndex]) {
						array[prevIndex + gap] = array[prevIndex];
						prevIndex -= gap;
					}
					array[prevIndex + gap] = current;
				}
				gap /= 2;
			}
		}
	}
	
	/**
	 * <p>归并排序
	 * <p>算法描述；
	 * <p>1、 把长度为n的输入序列分成两个长度为n/2的子序列； 
	 * <p>2、对这两个子序列分别采用归并排序； 
	 * <p>3、将两个排序好的子序列合并成一个最终的排序序列。
	 * <p>算法分析 最佳情况：T(n) = O(n) 最差情况：T(n) = O(nlogn) 平均情况：T(n) = O(nlogn)
	 * 
	 * @param array
	 */
	public static int[] mergeSort(int[] array) {
		int length = array.length;
		if (length == 0) {
			System.out.println("数组为空");
			return array;
		} else {
			int mid = length / 2;
			int[] left = Arrays.copyOfRange(array, 0, mid);
			int[] right = Arrays.copyOfRange(array, mid, array.length);
			int[] merge = merge(mergeSort(left), mergeSort(right));
			return merge;
		}
	}

	public static int[] merge(int[] left, int[] right) {
		int[] result = new int[left.length + right.length];
		for (int index = 0, i = 0, j = 0; index < result.length; index++) {
			if (i >= left.length)
				result[index] = right[j++];
			else if (j >= right.length)
				result[index] = left[i++];
			else if (left[i] > right[j])
				result[index] = right[j++];
			else
				result[index] = left[i++];
		}
		return result;
	}
	
	/**
	 * 快速排序 
	 * 算法描述：
	 * 1、 从数列中挑出一个元素，称为 “基准”（pivot）；
	 * 2、重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
	 * 3、递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。 
	 * 算法分析 最佳情况：T(n) = O(nlogn) 最差情况：T(n)= O(n2) 平均情况：T(n) = O(nlogn)
	 * 
	 * @param array
	 */
	public static int[] quickSort(int[] array, int start, int end) {
		if (array.length < 1 || start < 0 || end >= array.length || start > end)
			return null;
		int smallIndex = partition(array, start, end);
		if (smallIndex > start)
			quickSort(array, start, smallIndex - 1);
		if (smallIndex < end)
			quickSort(array, smallIndex + 1, end);
		return array;
	}

	public static int partition(int[] array, int start, int end) {
		int pivot = (int) (start + Math.random() * (end - start + 1));
		int smallIndex = start - 1;
		swap(array, pivot, end);
		for (int i = start; i <= end; i++)
			if (array[i] <= array[end]) {
				smallIndex++;
				if (i > smallIndex)
					swap(array, i, smallIndex);
			}
		return smallIndex;
	}

	public static void swap(int[] array, int i, int j) {
		int temp = array[i];
		array[i] = array[j];
		array[j] = temp;
	}
	
	/**
	 * 堆排序 
	 * 算法描述： 
	 * 1、将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
	 * 2、将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
	 * 3、由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
	 * 算法分析 最佳情况：T(n) = O(nlogn) 最差情况：T(n) = O(nlogn) 平均情况：T(n) = O(nlogn)
	 * 
	 * @param array
	 */
	static int heapSort_length;

	public static void heapSort(int[] array) {
		heapSort_length = array.length;
		if (heapSort_length == 0) {
			System.out.println("数组为空");
		} else {
			buildMaxHeap(array);
		}
	}

	public static void buildMaxHeap(int[] array) {
		for (int i = (heapSort_length / 2 - 1); i >= 0; i--) {
			adjustHeap(array, i);
		}
	}

	public static void adjustHeap(int[] array, int i) {
		int maxIndex = i;
		if (i * 2 < heapSort_length && array[i * 2] > array[maxIndex])
			maxIndex = i * 2;
		if (i * 2 + 1 < heapSort_length && array[i * 2 + 1] > array[maxIndex])
			maxIndex = i * 2 + 1;
		if (maxIndex != i) {
			swap(array, maxIndex, i);
			adjustHeap(array, maxIndex);
		}
	}
	
	/**
	 * 计数排序 
	 * 算法描述： 
	 * 1、找出待排序的数组中最大和最小的元素； 统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
	 * 2、对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
	 * 3、 反向填充目标数组：
	 * 4、将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。
	 * 算法分析 最佳情况：T(n) = O(n+k) 最差情况：T(n) = O(n+k) 平均情况：T(n) = O(n+k)
	 * 
	 * @param array
	 */
	public static void countingSort(int[] array) {
		int length = array.length;
		if (length == 0) {
			System.out.println("数组为空");
		} else {
			int bias, min = array[0], max = array[0];
			for (int i = 1; i < length; i++) {
				int iVaule = array[i];
				max = Math.max(max, iVaule);
				min = Math.min(max, iVaule);
			}
			bias = 0 - min;
			int[] bucket = new int[max - min + 1];
			Arrays.fill(bucket, 0);
			for (int i = 0; i < length; i++) {
				bucket[array[i] + bias]++;
			}
			int index = 0, i = bucket.length - 1;
			while (index < length) {
				if (bucket[i] != 0) {
					array[index] = i - bias;
					bucket[i]--;
					index++;
				} else {
					i--;
				}
			}
		}
	}
	
	/**
	 * 桶排序 
	 * 算法描述：
	 * 1、人为设置一个BucketSize，作为每个桶所能放置多少个不同数值（例如当BucketSize==5时，该桶可以存放｛1,2,3,4,5｝这几种数字，但是容量不限，即可以存放100个3）；
	 * 2、遍历输入数据，并且把数据一个一个放到对应的桶里去； 
	 * 3、对每个不是空的桶进行排序，可以使用其它排序方法，也可以递归使用桶排序；
	 * 4、从不是空的桶里把排好序的数据拼接起来。 
	 * 算法分析 最佳情况：T(n) = O(n+k) 最差情况：T(n) = O(n+k) 平均情况：T(n) = O(n2)
	 * 
	 * @param array
	 */
	public static ArrayList<Integer> bucketSort(ArrayList<Integer> array) {
		// 每个数组中桶的个数
		int bucketSize = 16;
		if (array.size() == 0) {
			System.out.println("数组为空");
			return array;
		} else {
			int min = array.get(0), max = array.get(0);
			for (int i = 1; i < array.size(); i++) {
				int iVaule = array.get(i);
				max = Math.max(max, iVaule);
				min = Math.min(max, iVaule);
			}

			int bucketCount = (max - min) / bucketSize + 1;
			ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketCount);
			ArrayList<Integer> resultArr = new ArrayList<>();
			for (int i = 0; i < bucketCount; i++) {
				bucketArr.add(new ArrayList<Integer>());
			}
			for (int i = 0; i < array.size(); i++) {
				bucketArr.get((array.get(i) - min) / bucketSize).add(array.get(i));
			}
			for (int i = 0; i < bucketCount; i++) {
				if (bucketSize == 1) { // 如果带排序数组中有重复数字时 感谢 @见风任然是风 朋友指出错误
					for (int j = 0; j < bucketArr.get(i).size(); j++)
						resultArr.add(bucketArr.get(i).get(j));
				} else {
					if (bucketCount == 1)
						bucketSize--;
					ArrayList<Integer> temp = bucketSort(bucketArr.get(i));
					for (int j = 0; j < temp.size(); j++)
						resultArr.add(temp.get(j));
				}
			}
			return resultArr;
		}
	}
	
	/**
	 * 基数排序 
	 * 算法描述： 
	 * 1、取得数组中的最大数，并取得位数； 
	 * 2、arr为原始数组，从最低位开始取每个位组成radix数组；
	 * 3、对radix进行计数排序（利用计数排序适用于小范围数的特点）； 
	 * 算法分析 最佳情况：T(n) = O(n * k)最差情况：T(n) = O(n * k) 平均情况：T(n) = O(n * k)
	 * 
	 * @param array
	 * @return
	 */
	public static void radixSort(int[] array) {
		if (array.length == 0) {
			System.out.println("数组为空");
		} else {
			int max = array[0];
			for (int i = 1; i < array.length; i++) {
				max = Math.max(max, array[i]);
			}
			int maxDigit = 0;
			while (max != 0) {
				max /= 10;
				maxDigit++;
			}
			int mod = 10, div = 1;
			ArrayList<ArrayList<Integer>> bucketList = new ArrayList<ArrayList<Integer>>();
			for (int i = 0; i < 10; i++)
				bucketList.add(new ArrayList<Integer>());
			for (int i = 0; i < maxDigit; i++, mod *= 10, div *= 10) {
				for (int j = 0; j < array.length; j++) {
					int num = (array[j] % mod) / div;
					bucketList.get(num).add(array[j]);
				}
				int index = 0;
				for (int j = 0; j < bucketList.size(); j++) {
					for (int k = 0; k < bucketList.get(j).size(); k++)
						array[index++] = bucketList.get(j).get(k);
					bucketList.get(j).clear();
				}
			}
		}
	}
}
